package binarySearch;

public class SearchInRotatedSortedArray33 {
    public int search(int[] nums, int target) {
        return search(0, nums.length - 1, nums, target);

    }

    private int search(int begin, int end, int[] nums, int target) {
        if (begin > end) {
            return -1;
        }
        int mid = (begin + end) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        if (nums[mid] >= nums[begin]) {
            if (target < nums[mid] && target >= nums[begin]) {
                return search(begin, mid - 1, nums, target);
            } else {
                return search(mid + 1, end, nums, target);
            }
        }

        if (nums[mid] < nums[begin]) {
            if (target > nums[mid] && target <= nums[end]) {
                return search(mid + 1, end, nums, target);
            } else {
                return search(begin, mid - 1, nums, target);
            }
        }
        return -1;
    }


//    public int search(int[] nums, int target) {
//        int begin = 0;
//        int end = nums.length - 1;
//        return searchRotated(begin, end, nums, target);
//
//    }
//
//    private int searchRotated(int begin, int end, int[] nums, int target) {
//        if (begin > end) {
//            return -1;
//        }
//
//        int mid = (begin + end) / 2;
//        if (nums[mid] == target) {
//            return mid;
//        }
//        if (nums[begin] == target) {
//            return begin;
//        }
//        if (nums[end] == target) {
//            return end;
//        }
//
//        if (nums[mid] > target && nums[begin] < target) {
//            return searchRotated(begin, mid, nums, target);
//        }
//
//        if (nums[mid] < target && target > nums[begin]) {
//            return searchRotated(begin, mid, nums, target);
//        }
//
//        if (nums[mid] < target && target < nums[end]) {
//            return searchRotated(mid, end, nums, target);
//        }
//
//        if (nums[mid] > target && nums[end] > target) {
//            return searchRotated(mid, end, nums, target);
//        }
//
//
//        return -1;
//    }
}
